10242. Путь коня

 

Задана шахматная доска n * n. Конь расположен в первой строке первого столбца пустой доски. Следуя шахматным правилам перемещения коня, посетите каждую клетку доски один раз.

Выведите состояние шахматной доски с ходами коня.

 

Вход. Размер шахматной доски n (1 ≤ n ≤ 8).

 

Выход. Выведите состояние шахматной доски с ходами коня. Если задача не имеет решения, выведите “Solution does not exist”.

 

Пример входа 1

Пример выхода 1

5

1  6 15 10 21

14  9 20  5 16

19  2  7 22 11

 8 13 24 17  4

25 18  3 12 23

 

 

Пример входа 2

Пример выхода 2

2

Solution does not exist

 

 

РЕШЕНИЕ

бектрекинг

 

Анализ алгоритма

Ходы коня нумеруем числами от 1 до n2. Объявим двумерный массив sol, в котором будем генерировать ходы коня. Стартуем с точки (0, 0), для которой положим sol[0][0] = 1 (первый ход коня). Далее перебираем позиции, куда может пойти шахматный конь. Если имеется позиция, куда может пойти конь, то совершаем туда ход и продолжаем поиск из нее. Если из текущей позиции совершить ход невозможно, то совершаем ход назад (бектрекинг) и продолжаем поиск. Поиск завершается, когда все числа от 1 до n2 будут расставлены на шахматной доске.

 

Реализация алгоритма

Максимальный размер шахмтной доски 8. В массиве sol генерируем ходы коня.

 

#define MAX 9

int sol[MAX][MAX];

 

Массивы xMove и yMove определяют возможные ходы коня. Если конь находится в клетке (x, y), то одним своим ходом он может пойти в клетку (x + xMove[i], y + yMove[i]), где 0 ≤ i ≤ 7.

 

int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };

int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

 

Функция isSafe проверяет, свободна ли клетка (x, y). То есть может ли конь пойти в клетку (x, y). Ответ утвердительный, если координаты x и y находятся в пределах шахматной доски (нумерация клеток идет с 0 до n – 1) и в клетку (x, y) еще не заходил конь (sol[x][y] = -1).

 

int isSafe(int x, int y)

{

  return (x >= 0 && x < n && y >= 0 && y < n && sol[x][y] == -1);

}

 

Функция printSolution выводит шахматную доску с ходами коня.

 

void printSolution(void)

{

  for (int x = 0; x < n; x++)

  {

    for (int y = 0; y < n; y++)

      printf("%2d ", sol[x][y]);

    printf("\n");

  }

}

 

Функция solveKTUtil совершает ход номер movei в клетку (x, y). Продолжаем поиск с возвратом из клетки (x, y) до тех пор пока не будет совершено n2 ходов.

 

int solveKTUtil(int x, int y, int movei)

{

 

В клетку (x, y) совершен ход номер movei.

 

  sol[x][y] = movei;

 

Если совершено n2 ходов, то завершаем поиск.

 

  if (movei == n * n) return 1;

 

Перебираем клетки, куда можно пойти из (x, y). Из клетки (x, y) одним ходом конь может пойти в (x + xMove[i], y + yMove[i]), где 0 ≤ i ≤ 7.

 

  for (int k = 0; k < 8; k++)

  {

    int next_x = x + xMove[k];

    int next_y = y + yMove[k];

 

Если в клетке (next_x, next_y) конь еще не был, то запускаем рекурсивно из нее перебор. В (next_x, next_y) совершается ход номер movei + 1.

 

    if (isSafe(next_x, next_y))

    {

      if (solveKTUtil(next_x, next_y, movei + 1) == 1) return 1;

    }

  }

 

Если все ходы коня перебраны, но совершить ход в свободную клетку не удалось, совершаем ход назад (бектрекинг), освобождая клетку (x, y) (sol[x][y] = -1).

 

  sol[x][y] = -1;

  return 0;

}

 

Функция solve строит маршрут коня используя бектрекинг. Функция возвращает 0, если построение маршрута невозможно. В случае существования нескольких ответов, функция генерирует один из них.

 

int solve()

{

 

Инициализируем результирующую матрицу sol.

 

  for (int x = 0; x < N; x++)

  for (int y = 0; y < N; y++)

    sol[x][y] = -1;

 

Шахматный конь начинает свой путь из левого верхнего угла. Функция solveKTUtil стартует генерацию пути из клетки (0, 0). В клетке (0, 0) будет записано число 1.

 

  if (solveKTUtil(0, 0, 1) == 0)

  {

    printf("Solution does not exist");

    return 0;

  }

  else

    printSolution();

 

  return 1;

}

 

Основная часть программы. Читаем размер шахматной доски n. Запускаем функцию solve – решение задачи.

 

scanf("%d", &n);

solve();